package chapter22;

import java.util.LinkedList;
import java.util.List;

/**
 * 基本图算法-拓扑排序
 * <p>
 * 条件：有向无环图
 * 如果图G包含边(u,v),则节点u在拓扑排序的中处于节点v的前面
 */
public class Topo {

    static int time = 0;

    public static LinkedList<Node> topoDfs(List<Node> V, Node[] G) {
        LinkedList<Node> topo = new LinkedList<>();
        time = 0;
        for (Node u : V) {
            if (G[u.key].color == Node.WHILE) {
                topoDfsVisit(G, G[u.key], topo);
            }
        }
        return topo;
    }

    public static void topoDfsVisit(Node[] G, Node u, LinkedList<Node> topo) {
        time = time + 1;
        u.d = time;
        u.color = Node.GRAY;
        // 遍历u相邻边的v
        Node next = u;
        while (next != null) {
            Node v = G[next.key];
            if (v != null && v.color == Node.WHILE) {
                v.p = u;
                topoDfsVisit(G, v, topo);
            }
            next = next.next;
        }
        u.color = Node.BLACK;
        time = time + 1;
        u.f = time;
        topo.addFirst(u);
    }
}
